package main

import "fmt"

// InsertSort 插入排序：属于插入类排序算法——稳定排序算法
func InsertSort(list []int) {
	n := len(list)

	for i := 1; i <= n - 1; i++ {
		deal := list[i]  // 待排序的数
		j := i - 1		 // 待排序的数左边的第一个数的位置

		// 如果第一次比较，比左边的已经排好序的第一个数小，那么进入比较插入逻辑块处理
		if deal < list[j] {
			// 一直往左边找，比待排序达的数都往后挪，腾出空位给待排序数插入
			for ; j >= 0 && deal < list[j]; j-- {
				list[j + 1] = list[j]
			}
			list[j + 1] = deal  // 结束，待排序数据插入空位
		}
	}
}



func main() {

	list := []int{5}
	InsertSort(list)
	fmt.Println(list)
	list1 := []int{5, 9}
	InsertSort(list1)
	fmt.Println(list1)
	list2 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	InsertSort(list2)
	fmt.Println(list2)

}



















